package org.example.BinaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Sequence_traversal_of_N_tree {
    public static List<List<Integer>> arr = new ArrayList<>();
    public static void main(String[] args) {
        //N 叉树的层序遍历

        //给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
        //树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node root = new Node(0);
        ArrayList<Node> nodes = new ArrayList<>();
        nodes.add(node1);
        nodes.add(node2);
        nodes.add(node3);
        root.children = nodes;
        ArrayList<Node> nodes2 = new ArrayList<>();
        nodes2.add(node4);
        nodes2.add(node5);
        nodes2.add(node6);
        node1.children = nodes2;
        ArrayList<Node> nodes3 = new ArrayList<>();
        nodes3.add(node7);
        node3.children = nodes3;
        get(root);
        System.out.print("[ ");
        for (List<Integer> list :arr){
            System.out.print("[ ");
            for (Integer i : list) {
                System.out.print(i+" ");
            }
            System.out.print("] ");
        }
        System.out.print("]");
    }
    //BFS迭代法
    public static void get(Node root) {
        if (root==null) return;
        ArrayDeque<Node> deque = new ArrayDeque<>();
        deque.add(root);
        while(!deque.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int len = deque.size();
            while(len>0){
                Node node = deque.poll();
                list.add(node.val);
                if (node.children!=null) deque.addAll(node.children);
                len--;
            }
            arr.add(list);
        }
    }
}
